# coding: utf8
# datetime: 2021-04-14
# 题目地址: https://leetcode-cn.com/problems/implement-trie-prefix-tree/


class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.childs = [None]*26
        self.isWord = False

    def searchPrefix(self, prefix: str) -> "Trie":
        node = self
        for ch in prefix:
            ch = ord(ch)-ord("a")
            if node.childs[ch] is None:
                return None
            node = node.childs[ch]
        return node
    
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self
        for ch in word:
            ch = ord(ch)-ord("a")
            if node.childs[ch] is None:
                node.childs[ch] = Trie()
            node = node.childs[ch]
        node.isWord = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.searchPrefix(word)
        if node and node.isWord:
            return True
        return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        return self.searchPrefix(prefix) is not None
